1. Field of the Invention
The invention relates to a method for reducing the computational complexity of a Viterbi decoder and, more particularly, to a method for reducing the computational complexity of a Viterbi decoder at all code rates of a convolutional code.
2. Description of Related Art
In current communication systems, a transmitter transmits a radio signal to a remote receiver. When the radio signal passes through a wireless channel so as to cause a fading and result in errors. Accordingly, the transmitted signal is typically performed with a convolutional encoding before being modulated to the RF signal. After demodulating the received radio signal, the remote receiver performs the convolutional decoding to thereby reconstruct the transmitted signal. Such a way can reduce the channel fading effect and noise interference. The convolutional encoding is referred to as a channel encoding, which is performed by a channel encoder. In general, a convolutional code has three parameters: the number of input bits k, the number of output bits n, and constraint length. The input and output bit parameters k and n are typically represented by the code rate k/n, where k, n are a positive integer. The constraint length indicates the number of memory element of the convolutional code. The convolutional decoding uses a Viterbi algorithm in order to provide an optimal coding gain. Therefore, the current communication systems mostly implements the Viterbi decoder to perform the convolutional decoding. The convolutional code can enhance the capability of error correction by increasing the constraint length. However, the decoding computation at the receiving side is increased with the increased constraint length. To overcome this, U.S. Pat. No. 5,539,757 granted to Cox, et al. for an “Error correction systems with modified Viterbi decoding” has disclosed a method to relatively reduce the computation of the Viterbi decoder by efficiently using the relation of the branches. However, the method can be applied only at a specific code rate, 1/n, which cannot satisfy a user with a desire for a code rate k/n other than the code rate 1/n.